package com.hot100.easy;

/**
 * @ClassName Demo05
 * @Description 爬楼梯
 * @Author zt
 * @Date 16:31 2022/6/8
 * @Version 1.0
 * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
 *每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
 **/
public class Demo05 {
    public static void main(String[] args) {

        System.out.println(climbStairs2(45));
    }
    public static int climbStairs(int n) {
        if(n<=0){
            return 0;
        }else if(n==1){
            return 1;
        }else if(n==2){
            return 2;
        }else {
            return climbStairs(n-1)+climbStairs(n-2);
        }
    }
    public static int climbStairs2(int n) {
        if(n<=0){
            return 0;
        }
        if(n<=1){
            return 1;
        }
        if(n<=2){
            return 2;
        }
       int[] nums=new int[n];
       nums[0]=1;
       nums[1]=2;
      for (int i = 2; i < nums.length; i++) {
          nums[i]=nums[i-1]+nums[i-2];
      }
      return nums[n-1];
    }
}